package p700;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Set;
import java.util.stream.Collectors;

public class Leetcode_752 {
    public static int openLock(String[] deadends, String target) {
        Set<String> set = Arrays.stream(deadends).collect(Collectors.toSet());
        if (set.contains("0000") || set.contains(target)) {
            return -1;
        }
        LinkedList<String> que = new LinkedList<>();
        que.offer("0000");
        int res = -1;
        while (!que.isEmpty()) {
            int n = que.size();
            res++;
            for (int i = 0; i < n; i++) {
                String s = que.pop();
                if (s.equals(target)) {
                    return res;
                }
                if (!set.contains(s)) {
                    set.add(s);
                    for (int j = 0; j < 4; j++) {
                        StringBuilder s1 = new StringBuilder(s);
                        StringBuilder s2 = new StringBuilder(s);
                        s1.setCharAt(j, s1.charAt(j) == '9' ? '0' : (char) ((int) s1.charAt(j) + 1));
                        s2.setCharAt(j, s2.charAt(j) == '0' ? '9' : (char) ((int) s2.charAt(j) - 1));
                        if (!set.contains(s1.toString())) {
                            que.add(s1.toString());
                        }
                        if (!set.contains(s2.toString())) {
                            que.add(s2.toString());
                        }
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(
                openLock(new String[]{
                        "0201", "0101", "0102", "1212", "2002"
                }, "0202")
        );
    }
}
